package pro.softzhang.algo.lc0;

import java.util.HashMap;
import java.util.Map;

/**
 * TODO 加练
 */
public class LC76_MinimumWindowSubstring {
    public static void main(String[] args) {
        String s = "ADOBECODEBANC", t = "ABC";
        String minStr = new LC76_MinimumWindowSubstring().minWindow(s, t);
        System.out.println(minStr);
    }

    public String minWindow(String s, String t) {
        Map<Character, Integer> counts = new HashMap<>();
        for (char ch : t.toCharArray()) {
            counts.put(ch, counts.getOrDefault(ch, 0) + 1);
        }

        int count = counts.size(), start = 0, end = 0, minStart = 0, minEnd = 0, minLength = Integer.MAX_VALUE;
        while (end < s.length() || (count == 0 && end == s.length())) {
            if(count > 0) {
                char endCh = s.charAt(end);
                if(counts.containsKey(endCh)) {
                    counts.put(endCh, counts.get(endCh) - 1);
                    if(counts.get(endCh) == 0) {
                        count--;
                    }
                }
                end++;
            } else {
                if(end - start < minLength) {
                    minLength = end - start;
                    minStart = start;
                    minEnd = end;
                }
                char startCh = s.charAt(start);
                if(counts.containsKey(startCh)) {
                    counts.put(startCh, counts.get(startCh) + 1);
                    if(counts.get(startCh) == 1) {
                        count++;
                    }
                }
                start++;
            }
        }

        return minLength < Integer.MAX_VALUE ? s.substring(minStart, minEnd) : "";
    }
}
